{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #3Sum Closest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: threeSumClosest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最接近的三数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组&nbsp;<code>nums</code><em>&nbsp;</em>和 一个目标值&nbsp;<code>target</code>。请你从 <code>nums</code><em> </em>中选出三个整数，使它们的和与&nbsp;<code>target</code>&nbsp;最接近。</p>\n",
    "\n",
    "<p>返回这三个数的和。</p>\n",
    "\n",
    "<p>假定每组输入只存在恰好一个解。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,2,1,-4], target = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,0,0], target = 1\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= target &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [3sum-closest](https://leetcode.cn/problems/3sum-closest/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [3sum-closest](https://leetcode.cn/problems/3sum-closest/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,2,1,-4]\\n1', '[0,0,0]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        dic={}\n",
    "        if len(nums)<3:\n",
    "            return sum(nums)\n",
    "        \n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-2):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            l = i + 1\n",
    "            r = len(nums) - 1\n",
    "            while l < r:\n",
    "                sum = nums[i] + nums[l] + nums[r]\n",
    "                if sum < target:\n",
    "                    l += 1\n",
    "                    dic[sum] = target - sum\n",
    "                elif sum > target:\n",
    "                    r -= 1\n",
    "                    dic[sum] = sum - target\n",
    "                else:\n",
    "                    return target\n",
    "        return min(dic,key=dic.get)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        tmp = float(\"inf\")\n",
    "        for i in range(len(nums) - 2):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            lo = i + 1\n",
    "            hi = len(nums) - 1\n",
    "            while lo < hi:\n",
    "                s = nums[i] + nums[lo] + nums[hi]\n",
    "                if abs(s - target) < tmp:\n",
    "                    result = s\n",
    "                    tmp = abs(s - target)\n",
    "                if s < target:\n",
    "                    lo += 1\n",
    "                elif s > target:\n",
    "                    hi -= 1\n",
    "                else:\n",
    "                    return target\n",
    "        return result\n",
    "\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        nums = sorted(nums)\n",
    "        if len(nums) < 3:\n",
    "            return []\n",
    "        i = 0\n",
    "        sum_num = nums[i] + nums[i + 1] + nums[i + 2]\n",
    "        closest = sum_num - target\n",
    "        while i < len(nums) - 2:\n",
    "            j = i + 1\n",
    "            k = len(nums) - 1\n",
    "\n",
    "            while j < k:\n",
    "                sum_num = nums[i] + nums[j] + nums[k]\n",
    "                close = sum_num - target\n",
    "\n",
    "                if close < 0:\n",
    "                    if abs(close) < abs(closest):\n",
    "                        closest = close\n",
    "                    j += 1\n",
    "                elif close > 0:\n",
    "                    if abs(close) < abs(closest):\n",
    "                        closest = close\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    return target\n",
    "            i += 1\n",
    "            while i < len(nums) and nums[i - 1] == nums[i]:\n",
    "                i += 1\n",
    "\n",
    "        return closest + target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        diffList = []\n",
    "        nums.sort()\n",
    "        result = ''\n",
    "        for i in range(len(nums)-2):\n",
    "            j = i + 1\n",
    "            k = len(nums) - 1\n",
    "            while j < k:\n",
    "                diff = nums[i] + nums[j] + nums[k]\n",
    "                diffList.append(diff)\n",
    "                if diff > target:\n",
    "                    k -= 1\n",
    "                elif diff < target:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    result = diff\n",
    "                    break\n",
    "            if result == diff:\n",
    "                break\n",
    "        else:\n",
    "            diffList = list(set(diffList))\n",
    "            item = [abs(x-target) for x in diffList]\n",
    "            result = diffList[item.index(min(item))]\n",
    "        return result      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        result,max_mm = 0,float('inf')\n",
    "        i = 0\n",
    "        while i < len(nums)-2:\n",
    "            if i == 0 or nums[i] != nums[i-1]:\n",
    "                j,k = i + 1, len(nums) - 1\n",
    "                while j < k:\n",
    "                    mm = nums[i] + nums[j] + nums[k] - target\n",
    "                    if abs(mm)<max_mm:\n",
    "                        max_mm = abs(mm)\n",
    "                        result = nums[i] + nums[j] + nums[k]\n",
    "                    if mm < 0:\n",
    "                        j += 1\n",
    "                    elif mm > 0:\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        return target\n",
    "            i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums)<3:\n",
    "            return 0\n",
    "        if len(nums) == 3:\n",
    "            return sum(nums)\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        tmp = nums[0] + nums[1] + nums[-1]\n",
    "        for i in range(len(nums)-2):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue                \n",
    "            j = i + 1\n",
    "            k = len(nums)-1 \n",
    "            while j < k:\n",
    "                res = nums[i] + nums[j] + nums[k]\n",
    "                \n",
    "                if abs(res-target) < abs(tmp - target):\n",
    "                    tmp = res\n",
    "                elif res < target:\n",
    "                    j += 1\n",
    "                elif res == target:\n",
    "                     return res\n",
    "                else:\n",
    "                    k -= 1\n",
    "        return tmp\n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        nums.sort()\n",
    "        init_num = float('inf')\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            left = i + 1\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                tmp_sum = nums[i] + nums[left] + nums[right]\n",
    "                abs_num = abs(target - tmp_sum)\n",
    "                \n",
    "                if abs_num <= init_num:\n",
    "                    init_num = abs_num\n",
    "                    result.append(tmp_sum)\n",
    "                    \n",
    "                if tmp_sum < target:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "            \n",
    "        return result[-1]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res=0\n",
    "        min_distance=9999\n",
    "        \n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        for i in range(len(nums)-2):\n",
    "            print('i:',i)\n",
    "            l=i+1\n",
    "            r=len(nums)-1\n",
    "            while(l<r):\n",
    "                sum = nums[i]+nums[l]+nums[r]\n",
    "                \n",
    "                if abs(target-sum)<min_distance:\n",
    "                    res=sum\n",
    "                    min_distance=abs(target-sum)\n",
    "                    print(i,l,r,sum)\n",
    "                    \n",
    "                if target==sum:\n",
    "                    return target\n",
    "                elif target>sum:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    r-=1\n",
    "                    \n",
    "\n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        nums.sort()\n",
    "        len_nums = len(nums)\n",
    "        \n",
    "        #这儿的res=None,而不是res等于一个数值\n",
    "        res = None\n",
    "        for i in range(len_nums-2): \n",
    "            j = i+1\n",
    "            k = len_nums-1\n",
    "            min = nums[0] + nums[1] + nums[2]\n",
    "            print(min)\n",
    "            max = nums[i] + nums[k] + nums[k-1]\n",
    "            if min > target:\n",
    "                res = min\n",
    "                break\n",
    "            elif max < target:\n",
    "            #     # if res == None:\n",
    "            #     #     res = max\n",
    "            #     # if abs(max-target) < abs(res-target):\n",
    "            #     #     res = max\n",
    "            #     #     print(max)\n",
    "                 res = max if res == None or abs(max-target) < abs(res-target) else res\n",
    "\n",
    "            else:\n",
    "                while j<k: \n",
    "                    s = nums[i]+nums[j]+nums[k]\n",
    "                    if res == None:\n",
    "                        res = s\n",
    "                    if abs(s-target) < abs(res-target):\n",
    "                        res = s\n",
    "                    if s == target:\n",
    "                        return s\n",
    "                    elif s > target:\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        nums.sort()\n",
    "        len_nums = len(nums)\n",
    "        best_dist = float('inf')\n",
    "        best_sum = 0\n",
    "        res = []\n",
    "        for key, value in enumerate(nums[:len_nums-2]):\n",
    "            l, r = key+1,len_nums-1\n",
    "            if nums[l] + nums[l+1] + value > target:\n",
    "                res.append(nums[l] + nums[l+1] + value)\n",
    "            elif nums[r] + nums[r-1] + nums[r-2] < target:\n",
    "                res.append(nums[l] + nums[l+1] + value)\n",
    "            while l < r:\n",
    "                tmp = value + nums[l] + nums[r]\n",
    "                res.append(tmp)\n",
    "                if tmp == target:\n",
    "                    return target\n",
    "                \n",
    "                # if abs(tmp-target) < best_dist:\n",
    "                #     best_dist = abs(tmp-target)\n",
    "                #     best_sum = tmp\n",
    "                if tmp < target:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        # res.append(best_sum)\n",
    "        res.sort(key = lambda x: abs(x - target))\n",
    "        return res[0]\n",
    "                    \n",
    "            \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        l = len(nums)\n",
    "        nums.sort()\n",
    "        x = []\n",
    "        for i in range(1, l-1):\n",
    "            start = 0\n",
    "            end = l-1\n",
    "            change = target - nums[i]\n",
    "            while start < i and end > i:\n",
    "                x.append(nums[start] + nums[end] - change)\n",
    "                if nums[start] + nums[end] > change:\n",
    "                    end -= 1\n",
    "                elif nums[start] + nums[end] < change:\n",
    "                    start += 1\n",
    "                else:\n",
    "                    return target\n",
    "        change_list = [abs(j) for j in x]\n",
    "        min_num = min(change_list)\n",
    "        return x[change_list.index(min_num)] + target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        if not nums or len(nums)<3:\n",
    "            return None\n",
    "        length = len(nums)\n",
    "        nums.sort()\n",
    "        ans =nums[0] + nums[1] + nums[2] \n",
    "\n",
    "        for i in range(length-2):\n",
    "            first = i + 1\n",
    "            last = length - 1\n",
    "            while first <last:\n",
    "                temp=nums[i]+nums[first]+nums[last]\n",
    "                if abs(temp - target) < abs(ans - target):\n",
    "                        ans = temp\n",
    "                if temp == target:\n",
    "                    return target\n",
    "                elif temp < target:\n",
    "                    first += 1\n",
    "                else:\n",
    "                    last -= 1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        res = nums[0] + nums[1] + nums[2]\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n - 2):\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j < k:\n",
    "                num_sum = nums[i] + nums[j] + nums[k]\n",
    "                if num_sum == target:\n",
    "                    return target\n",
    "                elif num_sum > target:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "                if abs(num_sum - target) < abs(res - target):\n",
    "                    res = num_sum\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            left = i + 1\n",
    "            right = n - 1\n",
    "            while left < right:  \n",
    "                cur = nums[i] + nums[left] + nums[right]\n",
    "                if cur == target:\n",
    "                    return target\n",
    "                if abs(cur - target) < abs(res - target):\n",
    "                    res = cur\n",
    "                if cur < target:\n",
    "                        left += 1\n",
    "                elif cur > target:\n",
    "                        right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        closest_sum = float('inf')\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-2):\n",
    "            start = i+1\n",
    "            end = len(nums)-1\n",
    "            while(start < end):\n",
    "                temp = nums[i] + nums[start] + nums[end]\n",
    "                if(temp == target):\n",
    "                    return temp\n",
    "                elif(temp > target):\n",
    "                    end -= 1\n",
    "                else:\n",
    "                    start += 1\n",
    "                if(abs(closest_sum-target) > abs(temp-target)):\n",
    "                    closest_sum = temp\n",
    "        return closest_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = sum(nums[0:3])\n",
    "        if ans > target:\n",
    "            return ans\n",
    "        if sum(nums[-3:]) < target:\n",
    "            return sum(nums[-3:])\n",
    "        for i in range(len(nums)-2):\n",
    "            left = i + 1\n",
    "            right = len(nums) - 1\n",
    "            while right > left:\n",
    "                _sum = nums[i] + nums[left] + nums[right]\n",
    "                if abs(_sum - target) < abs(ans-target):\n",
    "                    ans = _sum\n",
    "                if _sum > target:\n",
    "                    right -= 1\n",
    "                elif _sum < target:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    return _sum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        result = nums[0]+nums[1]+nums[2]\n",
    "        length = len(nums)\n",
    "        for i in range(length-2):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            left,right = i+1,length-1\n",
    "            while right > left:\n",
    "                temp = nums[i]+nums[left]+nums[right]\n",
    "                if abs(temp-target)<abs(result-target):\n",
    "                    result = temp\n",
    "                if temp - target>0:\n",
    "                    right = right - 1\n",
    "                    if nums[right] == nums[right+1]:\n",
    "                        continue\n",
    "                else:\n",
    "                    left = left + 1\n",
    "                    if nums[left] == nums[left-1]:\n",
    "                        continue\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "            nums.sort()\n",
    "            n = len(nums)\n",
    "            best = 10**7\n",
    "            def update(cur):\n",
    "                nonlocal best\n",
    "                if abs(cur - target) < abs(best - target):\n",
    "                    best = cur\n",
    "\n",
    "            for first in range(n):\n",
    "                if first > 0 and nums[first] == nums[first - 1]:\n",
    "                    continue\n",
    "                j, k = first + 1, n - 1\n",
    "                while j < k:\n",
    "                    s = nums[first] + nums[j] + nums[k]\n",
    "                    if s == target:\n",
    "                        return target\n",
    "                    update(s)\n",
    "\n",
    "                    if s > target:\n",
    "                        k0 = k - 1\n",
    "                        while j < k0 and nums[k] == nums[k0]:\n",
    "                            k0 -= 1\n",
    "                        k = k0\n",
    "                    else:\n",
    "                        j0 = j + 1\n",
    "                        while j0 < k and nums[j] == nums[j0]:\n",
    "                            j0 += 1\n",
    "                        j = j0\n",
    "            return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        if not nums or len(nums)<=2:\n",
    "            return\n",
    "        # if len(nums)==3:\n",
    "        #     return sum(nums)\n",
    "\n",
    "        nums.sort()\n",
    "        minsum = 1000000\n",
    "        res = 0\n",
    "        # res = []\n",
    "        for i in range(len(nums)-2):\n",
    "            m = i+1\n",
    "            n = len(nums)-1\n",
    "            while m<n:\n",
    "                tempsum = nums[i]+nums[m]+nums[n]\n",
    "                # print(nums[i],nums[m],nums[n])\n",
    "                # if tempsum==target:\n",
    "                #     return tempsum\n",
    "                if tempsum<target:\n",
    "                    m+=1\n",
    "                elif tempsum>target:\n",
    "                    n-=1\n",
    "                else:\n",
    "                    return tempsum\n",
    "                if abs(tempsum-target)<abs(minsum-target):\n",
    "                    minsum = tempsum\n",
    "\n",
    "        return minsum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\r\n",
    "        nums.sort()\r\n",
    "        min_res = 2**31\r\n",
    "        result = None\r\n",
    "        \r\n",
    "        for i in range(len(nums)):\r\n",
    "            l = i + 1\r\n",
    "            r = len(nums) - 1 \r\n",
    "            while l < r:\r\n",
    "                s = nums[i] + nums[l] + nums[r]\r\n",
    "                direction = target - s\r\n",
    "                res = abs(direction)\r\n",
    "\r\n",
    "                if res < min_res:\r\n",
    "                    min_res = res\r\n",
    "                    result = s\r\n",
    "               \r\n",
    "                if direction < 0:\r\n",
    "                    r -= 1\r\n",
    "                elif direction > 0:\r\n",
    "                    l += 1\r\n",
    "                else:\r\n",
    "                    return s\r\n",
    "\r\n",
    "                                \r\n",
    "                \r\n",
    "        return result\r\n",
    "\r\n",
    "            \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        ans = 10**7\n",
    "        def update(cur):\n",
    "            nonlocal ans\n",
    "            if abs(cur-target) < abs(ans-target) :\n",
    "                ans = cur\n",
    "            #print('s,ans',cur,ans)\n",
    "        for pa in range(n-2):\n",
    "            pb = pa + 1\n",
    "            pc = n - 1\n",
    "            while pb < pc :\n",
    "                print(pa,pb,pc)\n",
    "                s = nums[pa] + nums[pb] + nums[pc]\n",
    "                if s == target :\n",
    "                    return target\n",
    "                update(s)\n",
    "                if s > target: \n",
    "                    pc = pc - 1\n",
    "                    while pb < pc and nums[pc] == nums[pc+1] :\n",
    "                        pc -= 1\n",
    "                else : \n",
    "                    pb = pb + 1\n",
    "                    while pb < pc and nums[pb] == nums[pb-1] :\n",
    "                        pb += 1 \n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        ###三个数的和，与target相减，取最小的那个\n",
    "        #三重循环，时间复杂度太高\n",
    "        ##怎么做呢？\n",
    "        ##数组排序，固定一个数？加双指针移动？\n",
    "        n=len(nums)\n",
    "        \n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        if n<3:return 0\n",
    "\n",
    "        for i in range(len(nums)-2):\n",
    "            l=i+1\n",
    "            r=n-1\n",
    "            value=nums[i]+nums[l]+nums[r]-target\n",
    "         \n",
    "            res.append(value)\n",
    "            while l<r:\n",
    "                if value==0:\n",
    "                    return nums[i]+nums[l]+nums[r]\n",
    "                while (value>0 and l<r):\n",
    "                    r=r-1\n",
    "                    if l<r:\n",
    "                        value=nums[i]+nums[l]+nums[r]-target\n",
    "                        res.append(value)\n",
    "                while (value<0 and l<r):\n",
    "                    l=l+1\n",
    "                    if l<r:\n",
    "                        value=nums[i]+nums[l]+nums[r]-target\n",
    "                        res.append(value)\n",
    "\n",
    "        abs_res=[abs(i) for i in res]\n",
    "        min_value=min(abs_res)\n",
    "        result=res[abs_res.index(min_value)]+target\n",
    "        \n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums)<=3:\n",
    "            return sum(nums)\n",
    "        nums.sort()\n",
    "        if sum(nums[-3:])<=target:\n",
    "            return sum(nums[-3:])\n",
    "        last_error=nums[0]+nums[1]+nums[2]-target\n",
    "        if last_error>=0:\n",
    "            return nums[0]+nums[1]+nums[2]\n",
    "        length=len(nums)\n",
    "        result=[last_error]\n",
    "        flag=False\n",
    "        for i in range(length-2):\n",
    "            for j in range(i+1,length-1):\n",
    "                for k in range(j+1,length):\n",
    "                    current=nums[i]+nums[j]+nums[k]\n",
    "                    error=current-target\n",
    "                    if error==0:\n",
    "                        return current\n",
    "                    elif error>0:\n",
    "                        if k>j+1:\n",
    "                            if abs(last_error)>error:\n",
    "                                result.append(error)\n",
    "                            else:\n",
    "                                result.append(last_error)\n",
    "                        else:\n",
    "                            result.append(error)\n",
    "                        break\n",
    "                    last_error=error\n",
    "                result.append(error) #if all is less than 0\n",
    "\n",
    "        min_error=result[0]\n",
    "        for index in range(1,len(result)):\n",
    "            error=result[index]\n",
    "            if abs(error)<abs(min_error):\n",
    "                min_error=error\n",
    "    \n",
    "        return target+min_error"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:       \n",
    "        nums=sorted(nums)\n",
    "        res=sum(nums[:3])\n",
    "        for i in range(len(nums)-2):\n",
    "            left = i+1\n",
    "            right=len(nums)-1\n",
    "            while left<right:\n",
    "                if nums[i]+nums[left]+nums[right]-target==0:\n",
    "                    return nums[i]+nums[left]+nums[right]\n",
    "                if abs(nums[i]+nums[left]+nums[right]-target)<abs(res-target):\n",
    "                    res=(nums[i]+nums[left]+nums[right])\n",
    "                    continue\n",
    "                if nums[i]+nums[left]+nums[right]-target>0:\n",
    "                    right-=1\n",
    "                    continue\n",
    "                if nums[i]+nums[left]+nums[right]-target<0:\n",
    "                    left+=1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        dis = 10 ** 5\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n-2):\n",
    "            left = i + 1\n",
    "            right = n - 1\n",
    "            \n",
    "            while left < right:\n",
    "                s = nums[left] + nums[right] + nums[i]\n",
    "                if abs(s - target) < dis:\n",
    "                    res = s\n",
    "                    dis = abs(s - target)\n",
    "\n",
    "                if s > target:\n",
    "                    right -= 1\n",
    "                elif s < target:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    return target\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = nums[0] + nums[1]+ nums[2]\n",
    "        for i in range(len(nums)):\n",
    "            l = i + 1\n",
    "            r = len(nums) - 1\n",
    "            while l < r:\n",
    "                sums = nums[i]+ nums[l]+ nums[r]\n",
    "                if abs(target - sums) < abs(target - res):\n",
    "                    res = sums\n",
    "\n",
    "                if target > sums:\n",
    "                    l += 1\n",
    "                    \n",
    "                elif target < sums:\n",
    "                    r -= 1\n",
    "\n",
    "                else:\n",
    "                    return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        ret = float('inf')\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "        for i in range(length - 2):\n",
    "            left = i + 1\n",
    "            right = length - 1\n",
    "            while left < right:\n",
    "                tmp = nums[i] + nums[left] + nums[right]\n",
    "                ret = tmp if abs(tmp - target) < abs(ret - target) else ret\n",
    "                if tmp == target:\n",
    "                    return target\n",
    "                if tmp > target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        nums_len = len(nums)\n",
    "        ans, total_num = 99999999, 99999999\n",
    "        for i in range(nums_len):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            left = i + 1\n",
    "            right = nums_len - 1\n",
    "            while left < right:\n",
    "                total = nums[i] + nums[left] + nums[right]\n",
    "                diff = self.calculate_difference(target, total)\n",
    "                if diff == 0:\n",
    "                    return total\n",
    "                if ans > diff:\n",
    "                    ans = diff\n",
    "                    total_num = total\n",
    "                if total > target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "\n",
    "        return total_num\n",
    "                \n",
    "    \n",
    "    def calculate_difference(self, num1: int, num2: int):\n",
    "        if num1 >= num2:\n",
    "            return num1 -num2\n",
    "        return num2 - num1\n",
    "\n",
    "\n",
    "# -10 -7 -2 0 4 8 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        re_min = 0 #存储当前最小的差值\n",
    "        \n",
    "        for i in range(n):\n",
    "            low = i+1\n",
    "            high = n-1\n",
    "            while low < high:\n",
    "                three_sum = nums[i] + nums[low] + nums[high]\n",
    "                x = target - three_sum #当前三数的差值\n",
    "                if re_min == 0:\n",
    "                    re_min = abs(x)\n",
    "                    sum_min = three_sum #sum_min为当前最接近的和\n",
    "                \n",
    "                if abs(x) < re_min:\n",
    "                    re_min = abs(x)\n",
    "                    sum_min = three_sum\n",
    "                \n",
    "                if three_sum == target:\n",
    "                    return target\n",
    "                elif three_sum < target:\n",
    "                    low += 1\n",
    "                else:\n",
    "                    high -= 1\n",
    "        \n",
    "        return sum_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        best = float(\"inf\")\n",
    "\n",
    "        def update(cur):\n",
    "            nonlocal best\n",
    "            if abs(cur-target) < abs(best-target):\n",
    "                best = cur\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i>0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            j, k = i+1, n-1\n",
    "            while j<k:\n",
    "                total = nums[i] + nums[j] + nums[k]\n",
    "                if total == target:\n",
    "                    return target\n",
    "                update(total)\n",
    "                if total>target:\n",
    "                    k = k-1\n",
    "                    while j<k and nums[k] == nums[k+1]:\n",
    "                        k -= 1\n",
    "                else:\n",
    "                    j = j+1\n",
    "                    while j<k and nums[j] == nums[j-1]:\n",
    "                        j += 1\n",
    "        return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        for i, v in enumerate(nums):\n",
    "            j, k = i + 1, n - 1\n",
    "            while j < k:\n",
    "                t = v + nums[j] + nums[k]\n",
    "                if t == target:\n",
    "                    return t\n",
    "                if abs(t - target) < abs(ans - target):\n",
    "                    ans = t\n",
    "                if t > target:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        nlen = len(nums)\n",
    "        minb = float('inf')\n",
    "        for i in range(nlen):\n",
    "            a = nums[i]\n",
    "            pb = i + 1\n",
    "            pc = nlen - 1\n",
    "            while pb < pc:\n",
    "                tmp = a + nums[pb] + nums[pc]\n",
    "                if tmp > target:\n",
    "                    pc -= 1\n",
    "                elif tmp < target:\n",
    "                    pb += 1\n",
    "                else:\n",
    "                    return tmp\n",
    "                bias = tmp - target\n",
    "                if abs(bias) < minb:\n",
    "                    minb = abs(bias)\n",
    "                    ans = bias + target\n",
    "\n",
    "        return ans\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
